#include<stdio.h>
#include<string.h>
//#include<algorithm>
//#include<iostream>
#include<math.h>
#include<stdbool.h>
//using namespace std;
int n;
int main(){
    while(scanf("%d",&n)!=EOF){
        int k = sqrt(n);
        bool flag = false;
        for(int i = 2; i <= k; i ++){
            if(n % i == 0){
                flag = true;
                break;
            }
        }
        if(!flag) printf("1\n");
        else{
            if(n % 2 == 0) printf("2\n");
            else{
                int t = n - 2;
                int kk = sqrt(t);
                flag = false;
                for(int i = 2; i <= kk; i ++){
                    if(t % i == 0){
                        flag = true;
                        break;
                    }
                }
                if(flag) printf("3\n");
                else printf("2\n");
            }
        }
    }
    return 0;
}
